Java 集合类学习 Set 集合

Set集合

Set 集合与 List 集合的区别就是，Set 集合的元素不能重复，而且无法保证顺序（有顺序的叫做 SortedSet），Set 实际上相当于只存储 key、不存储 value 的 Map。

public static void main(String[] args) {
    Set<String> set = new HashSet<>();
    set.add("你好");
    set.add("集合");
    set.add("世界");

    if (!set.add("你好")) {
        System.out.println("插入失败");
    }

    set.forEach(System.out::print); // Set的无序特点，所以输出是无序的
}

-->
插入失败
集合你好世界

值得注意的是：把 HashSet 换成 TreeSet，在遍历 TreeSet 时（TreeSet 继承自 SortedSet），输出就是有序的，但是这个顺序是元素的排序顺序，不是插入顺序：

public static void main(String[] args) {
    Set<String> set = new TreeSet<>();
    set.add("apple");
    set.add("danana");
    set.add("cear");
    set.add("brange");

    for (String s : set) {
        System.out.println(s);
    }
}

-->
apple
brange
cear
danana

HashSet

基于 HashCode 实现元素不重复

equals 方法可用于保证元素不重复，但如果每增加一个元素就检查一次，若集合中现在已经有 1000 个元素，那么第 1001 个元素加入集合时，就要调用 1000 次 equals 方法。这显然会大大降低效率。于是 HashSet 采用了哈希表的原理。

哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的HashCode 方法，就一下子能定位到它应该放置的物理位置上。

注：这里生成的 HashCode 并不是直接用作内存地址（在 table 里面的位置），而是需要拿到这个 HashCode 当作值进行二次计算才能取得内存地址，实际上 HashMap 那一块就已经说的很明确了参考这里如何取得元素在 table 里的位置

如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；
如果这个位置上已经有元素了，就调用它的 equals 方法与新元素进行比较，相同的话就不存了；
不相同的话，也就是发生了 Hash key 相同导致冲突的情况，那么就在这个 Hash key 的地方产生一个链表，将所有产生相同 HashCode 的对象放到这个单链表上去，串在一起。这样一来实际调用 equals 方法的次数就大大降低了，几乎只需要一两次。

从 Object 角度看，JVM 每 new 一个 Object，它都会将这个 Object 丢到一个 Hash 表中去，这样的话，下次做 Object 的比较或者取这个对象的时候（读取过程），它会根据对象的 HashCode 再从 Hash 表中取这个对象。这样做的目的是提高取对象的效率。若 HashCode 相同再去调用 equal

总之就是要给对象重新写 equals 和 hashCode 方法

// 自己定义一个 HashCodeClass 
public class HashCodeClass {
    private String str0;
    private double dou0;
    private int    int0;

    @Override
    public int hashCode() {
        return Objects.hash(str0, dou0, int0);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof HashCodeClass) {
            HashCodeClass hcc = (HashCodeClass)obj;

            if (hcc.str0.equals(this.str0) &&
                hcc.dou0 == this.dou0 &&
                hcc.int0 == this.int0) {
                return true;
            }
            return false;
        }
        return false;
    }
}

LinkedHashSet

前面说过，HashSet 优点在于插入速度很快，但是却没有顺序可言。如果需要保持插入顺序，可以使用这个 LinkedHashSet 它内部维护了一个链表用来记录插入的元素顺序，即FIFO(First Input First Output 先进先出)

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

LinkedHashSet 类的使用方法和 HashSet 基本一样

只是输出的顺序是按照插入顺序来的

public static void main(String[] args) {
    LinkedHashSet<Temp> temps = new LinkedHashSet<>();
    temps.add(new Temp(18,"张三"));
    temps.add(new Temp(18,"张三"));
    temps.add(new Temp(14, "王二"));
    temps.add(new Temp(12, "赵六"));
    temps.forEach(System.out::println);
}

TreeSet

和普通的 HashSet 不一样，普通的 HashSet 元素存取的时间复杂度一般是 $O(1)$ 的范围，而 TreeSet 是基于 TreeMap 实现的，TreeMap 内部对元素的操作复杂度为 $O(logn)$ ,所以 TreeSet 是红黑树实现的，TreeSet 中的数据是自动排好序的，不允许放入 null 值。

注意 TreeSet 判断两个对象不相等的方式是两个对象通过 equals 方法返回 false，或者通过 CompareTo 方法比较没有返回 0

那为什么要使用 TreeSet 呢？

因为 TreeSet 是 SortedSet 接口的唯一实现类，TreeSet 可以确保集合元素处于排序状态。TreeSet 支持两种排序方式，自然排序和定制排序（就是用 Comparator 接口），其中自然排序为默认的排序方式。自然排序使用要排序元素的 CompareTo(Object obj) 方法来比较元素之间大小关系，然后将元素按照升序排列（所以对象必须实现 Comparable 接口）

obj1.compareTo(obj2) 方法如果返回 0，则说明被比较的两个对象相等，如果返回一个正数，则表明 obj1 大于 obj2，如果是负数，则表明 obj1 小于 obj2。

public class Temp implements Comparable<Temp> {
    private int age;
    private String name;

    public Temp(int age, String name) {
        this.age = age;
        this.name = name;
    }


    public static void main(String[] args) {
        // 自然排序
        TreeSet<Temp> set = new TreeSet<>();
        set.add(new Temp(18, "张三"));
        set.add(new Temp(14, "王二"));
        set.add(new Temp(12, "赵六"));
        set.forEach(System.out::println);

        System.out.println("-----------------------------------------------");
        // 自定义排序
        TreeSet<Temp> set2 = new TreeSet<>(new Comparator<Temp>() {
            @Override
            public int compare(Temp o1, Temp o2) {
                return o1.age - o2.age;
            }
        });
        set2.add(new Temp(18, "张三"));
        set2.add(new Temp(14, "王二"));
        set2.add(new Temp(12, "赵六"));
        set2.forEach(System.out::println);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Temp temp = (Temp) o;
        return age == temp.age &&
                Objects.equals(name, temp.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

    @Override
    public int compareTo(Temp o) {
        return this.age - o.age;
    }


    @Override
    public String toString() {
        return "Temp{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

}

两种排序方式输出的结果是一样的

Temp{age=12, name='赵六'}
Temp{age=14, name='王二'}
Temp{age=18, name='张三'}
-----------------------------------------------
Temp{age=12, name='赵六'}
Temp{age=14, name='王二'}
Temp{age=18, name='张三'}

Set集合​

HashSet​

LinkedHashSet​

TreeSet​

Set集合

HashSet

LinkedHashSet

TreeSet